// ST表 - 0/1序列
//直接维护最长不下降子序列长度不现实, 没有数据结构可以直接维护, 三种情况
//1.区间全是0 -> f[r] - f[l - 1]
//2.区间全是1 -> g[r] - g[l - 1]
//3.区间左0右1 -> f[k] - f[l - 1] + g[r] - g[k], k从[l, r), 维护新的序列 f[k] - g[k] 即可

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e6 + 10;
int f[N]; //[1, i] 0 的个数
int g[N]; //[1, i] 1 的个数
int h[N]; //[1, i] "01" 的个数
int n, m;
int a[N];
int st[N][20]; //st[i][j]表示以i位置为起点, 长度为2^j的序列的最大值

int read()
{
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    int ret = 0;
    while(ch >= '0' && ch >- '9')
    {
        ret = ret * 10 + ch -'0';
        ch = getchar();
    }
    return ret;
}

void write(int x)
{
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
    {
        // cin >> a[i];
        a[i] = read();
        f[i] = f[i - 1] + (a[i] == 0);
        g[i] = g[i - 1] + (a[i] == 1);
        h[i] = h[i - 1] + (a[i] == 1 && a[i - 1] == 0);
        st[i][0] = f[i] - g[i];
    }

    for(int j = 1; (1 << j) <= n; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j-1]);

    while(m--)
    {
        int op, l, r; //cin >> op >> l >> r;
        op = read(), l = read(), r = read();
        if(op == 1) //最长不下降
        {
            int ret = max(f[r] - f[l - 1], g[r] - g[l - 1]);
            int k = log2(r - l + 1);
            ret = max(ret, max(st[l][k], st[r - (1 << k) + 1][k]) + g[r] - f[l - 1]); 
            // cout << ret << endl;
            write(ret);
            putchar('\n');
        }
        else //最长上升
        {
            write(h[r] == h[l] ? 1 : 2);
            putchar('\n');
        }
    }
    return 0;
}